二叉树的后序遍历

发表于 | 分类于 |
字数统计: 613 字 | 阅读时长 ≈ 2 分钟

题目描述：给定一个二叉树，返回它的 后序 遍历。

示例:
输入: [1,null,2,3]
1

2
/
3

输出: [3,2,1]

方法一：迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
  public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if(root == null) return res;

    Deque<TreeNode> stack = new LinkedList<>();
    TreeNode pre = null;//用于记录前一个访问的结点

    while(root != null || !stack.isEmpty()){
      while(root != null){
        stack.push(root);
        root = root.left;
      }
      root = stack.pop();
      if(root.right == null || root.right == pre){
        res.add(root.val);//访问
        pre = root;//更新
        root = null;//使得下一次循环直接出栈下一个
      }else{
        stack.push(root);//再次压回栈
        root = root.right;//访问右子树
      }     
    }
    return res;
  }
}

// 先遍历右子树，再遍历左子树
// h
var postorderTraversal = function(root) {
  let res = [], stack = []
  while(root || stack.length) {
    while(root) {
      res.unshift(root.val)
      stack.push(root)
      root = root.right
    }
    root = stack.pop()
    root = root.left
  }
  return res
};

复杂度分析

  • 时间复杂度：O(n)，其中 n 是二叉搜索树的节点数。每一个节点恰好被遍历一次。
  • 空间复杂度：O(n)，为迭代过程中显式栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为 O(n)。

执行结果：通过

  • 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗：36.6 MB, 在所有 Java 提交中击败了68.52%的用户

方法二：递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<Integer>();
    postorder(root, res);
    return res;
  }

  public void postorder (TreeNode root, List<Integer> res) {
    if(root == null) return;
    postorder(root.left, res);
    postorder(root.right, res);
    res.add(root.val);
  }
}

var postorderTraversal = function(root) {
    let res = []
    postorder(root, res)
    return res
};
var postorder = function(root, res) {
    if(root === null) return
    postorder(root.left, res)
    postorder(root.right, res)
    res.push(root.val)
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 是二叉搜索树的节点数。每一个节点恰好被遍历一次。

  • 空间复杂度：O(n)，为递归过程中栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为 O(n)。

执行结果：通过

  • 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗：36.3 MB, 在所有 Java 提交中击败了97.98%的用户